1. Field of the Invention
This invention relates to data encryption, and more particularly to a method and apparatus for varying the computational overhead associated with encrypting and decrypting digital data signals by selectively reusing, according to the desired level of security, a pseudorandom encoding sequence at the transmitter end and by storing and reusing pseudorandom decoding sequences at the receiver end.
2. Description of the Background Art
Data encryption is a function that ensures the privacy of a digital communication by preventing an unauthorized receiver from understanding the contents of a transmitted message. A conventional "symmetric key" cryptosystem is generally illustrated in FIG. 1(a). A transmitter transforms a plaintext message into ciphertext using an invertible encryption transformation. This transformation is a function of the plaintext input message and a secret key which is shared by both the transmitter and the receiver. The ciphertext is then transmitted over an unsecured public channel and the intended receiver of the message, also in possession of the secret key, applies the inverse transformation to decrypt the ciphertext and recover the original plaintext message. The secret key is communicated to a plurality of authorized users through a secure channel (for example, a secure Key Exchange Algorithm may be employed) and the key effectively dictates a specific encryption transformation from a family of cryptographic transformations. In general, any station in possession of the secret key may encrypt or decrypt messages.
A conventional cryptosystem can be said to exhibit "unconditional security" if the secret key is as long as the ciphertext message, each key is used only once, and all keys are equally likely. However, since most systems can be expected to transmit a large number of messages, the problem of distributing the key information becomes formidable. Most practical cryptosystems have short keys compared to the length of a message. The lessened security resulting from short keys is compensated for by relying on the complexity of the way that the key is combined with the data.
A particular example of a conventional cryptosystem, hereafter referred to as an electronic codebook, is generally illustrated in FIG. 1(b). The electronic codebook involves the use of a secret key that is shared by both the transmitter and the receiver. The transmitter utilizes the key to generate a deterministic, apparently random sequence of binary digits using a Pseudorandom Number (PN) generator. An essential feature of the PN generator is that with a specific key input, a unique PN sequence of arbitrary length may be generated. The PN sequence is then combined with the binary representation of the plaintext message to be encrypted to produce a sequence of ciphertext. The combination of the PN sequence and the plaintext must be accomplished using an invertible function. An invertible function is one that has a known inverse such that when the inverse function is applied to the ciphertext the original plaintext can be extracted. For example, two's complement addition or bit-wise exclusive-OR (XOR) are two widely used invertible functions, although other functions can be employed.
Decoding of the encrypted ciphertext may be performed by the receiver using a method identical to that used by the transmitter. Ciphertext is received from the transmitter and combined using a logical XOR gate, with a pseudorandom sequence generated by a PN generator identical to that used in the transmitter. The essence of the electronic codebook system is that an encryption key is used to generate a pseudorandom sequence in the transmitter side, and the identical sequence is then generated in the receiver when the same encryption key is applied to the receiver PN generator. The XOR gate in the receiver provides the inverse function of the XOR gate in the transmitter so that logical combination of the ciphertext and the PN sequence in the receiver produces the same plaintext that was originally encoded by the transmitter.
One drawback of the prior art system described is that the overhead of generating PN sequences is quite high, particularly relative to the overhead of applying the combination function. In practice, it is typical to generate and combine the PN sequence with a plaintext message of arbitrary length one character at a time, as needed. The characters of the PN sequence are discarded after a single use, so there is no opportunity to spread the cost of computing the sequence over several messages. The rate at which messages can be encrypted and decrypted is therefore limited by the speed at which the PN sequence can be produced. What is needed is a method for storing and reusing PN sequences in order to increase the transmission rate of messages through the cryptosystem.
Another drawback of the prior art system is that the receiver's PN generator may lose synchronization with that of the transmitter under some circumstances, necessitating additional recovery procedures in order for the plaintext to be recovered. For example, if the next character emitted by the PN generator is a function of the initial key input as well as the number of characters that have been previously emitted, and if the message is being communicated from the transmitter to the receiver in several fragments or packets, and if any packets are lost or received out of order, then it will first be necessary for the receiver to receive and arrange all the fragments in the proper order before decoding of the message can be accomplished. It is therefore desirable that a high speed cryptosystem exhibit the property of self-synchronization between transmitter and receiver such that no additional recovery procedures are required to decode messages.